package com.zjsru.oneDay;

import java.util.ArrayList;
import java.util.List;

/***
 *
 * 最简分数
 *
 * 输入：n = 2
 * 输出：["1/2"]
 * 解释："1/2" 是唯一一个分母小于等于 2 的最简分数。
 *
 * 输入：n = 4
 * 输出：["1/2","1/3","1/4","2/3","3/4"]
 * 解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。
 *
 */
public class simplifiedFractions {
    //如何快速判断两个数组成的分数是否为最简（即判断两个数的最大公约数是否为 1）。
    public List<String> simplifiedFractions(int n) {
        List<String> ans = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (gcd(i, j) == 1) {
                    ans.add(i + "/" + j);
                }
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

//    int gcd(int a, int b) { // 更相减损法
//        while (true) {
//            if (a > b) a -= b;
//            else if (a < b) b -= a;
//            else return a;
//        }
//    }

    public static void main(String[] args) {
        simplifiedFractions simplifiedFractions = new simplifiedFractions();
        int n = 4;
        System.out.println(simplifiedFractions.simplifiedFractions(n));
    }
}
